P5496 【模板】回文自动机(PAM)

不懂回文自动机的可以看这篇博客

现在默认大家都懂,用 Cnt[i]Cnt[i] 表示以 ii 结尾的回文串的个数。

由于 Link[i]Link[i] 表示 ii 的最长回文后缀,所以 Cnt[i]=Cnt[Link[i]]+1Cnt[i]=Cnt[Link[i]]+1(加上 ii 点所标示的一个回文串)

在构造回文自动机时处理出来即可。

#include <cstdio>
#include <cstring>

const int MAXN = 500000 , MAXK = 26;
char str[ MAXN + 5 ];
struct Palindrome_Automaton{
	int Size , Last , Root0 , Root1 , Trans[ MAXN + 5 ][ MAXK + 5 ] , Link[ MAXN + 5 ];
	int Len[ MAXN + 5 ] , Cnt[ MAXN + 5 ];
	
	Palindrome_Automaton( ) {
		Root0 = Size ++ , Root1 = Size ++; Last = Root1;
		Len[ Root0 ] = 0  , Link[ Root0 ] = Root1;
		Len[ Root1 ] = -1 , Link[ Root1 ] = Root1; 
	}
	void Extend( int ch , int dex ) {
		int u = Last;
		for( ; str[ dex - Len[ u ] - 1 ] != str[ dex ] ; u = Link[ u ] );
		if( !Trans[ u ][ ch ] ) {
			int Newnode = ++ Size , v = Link[ u ];
			Len[ Newnode ] = Len[ u ] + 2;
			
			for( ; str[ dex - Len[ v ] - 1 ] != str[ dex ] ; v = Link[ v ] );
			Link[ Newnode ] = Trans[ v ][ ch ] , Trans[ u ][ ch ] = Newnode;
			Cnt[ Newnode ] = Cnt[ Link[ Newnode ] ] + 1;
		}
		Last = Trans[ u ][ ch ];
	}
	
	void Build( char *str ) {
		int len = strlen( str );
		for( int i = 0 ; i < len ; i ++ ) {
			Extend( str[ i ] - 'a' + 1 , i );
			str[ i + 1 ] = ( str[ i + 1 ] - 97 + Cnt[ Last ] ) % 26 + 97;
			printf("%d ",Cnt[ Last ]);
		}	
	}
}PAM;

int main( ) {
	scanf("%s", str );
	PAM.Build( str );
	return 0;
}